Day5. 陣列(Array) - 題目實作(下)

15th鐵人賽

雜食性的貓

2023-09-20 21:01:24

483 瀏覽

分享至

看到狗狗有沒有讓心情變好呀，每隻狗狗都有不同顆數的球，就像陣列裡面可以裝不同元素一樣呢。
讓我們繼續昨天的進度、開始今天其他陣列相關算法的解題實作吧。

前綴和

Range Sum Query - Immutable
這題就是要讓我們實作一個 Class，Class 有兩個方法，第一是建構，會傳入一個整數陣列，第二是 SumRange，傳入一個左指針和右指針，要求回傳左到右間的數字加總。
暴力的寫法就是每次呼叫 SumRange 就老老實實從左遍歷到右，把數字加起來，這樣花的時間是 O(n)。透過前綴和算法，我們能在建構的時候花 O(n) 的時間去建構，相對的，每次呼叫 SumRange 所需的時間就變成了 O(1)。

先處理建構式，我們定義一個另外的整數陣列 rangeSum 來裝和數
在這個陣列裡，rangeSum[i] 表示 0 - i 的 nums 元素總和，遍歷傳入的 nums[] 陣列來完成這點，只要每次遍歷到下一個元素就持續加總就行
這樣的話，當處理 SumRange 的時候，我們只要拿出 rangeSum[right] 提前算好的數字，表示從開頭到 right 的加總，減去 rangeSum[left-1] 開頭到區間前一個的加總(另外判斷 left = 0 的狀況)，就會變成 left 到 right，所求區間的加總，成功降低了這個方法的時間複雜度

public class NumArray {
    private int[] rangeSum;
    public NumArray(int[] nums) {
        rangeSum = new int[nums.Length];
        rangeSum[0] = nums[0];
        for(var i = 1; i < nums.Length; i++){
            rangeSum[i] = rangeSum[i-1] + nums[i];
        }
    }
    
    public int SumRange(int left, int right) {
        return rangeSum[right] - (left == 0 ? 0 : rangeSum[left-1]);
    }
}

這題很好的展現了前綴和的妙用，降低了頻繁需要得知區間結果的時間複雜度。當題目所求與區間累加值相關，前綴和就會是一個要想起的選項。

差分陣列

Car Pooling
這個題目是一個情境題，有一輛車給定一個載客量，接下來給出數個陣列表示乘客上下車[乘客數，上車點，下車點]，考量這台車能不能在一趟(只往里程遞增移動)的情況下載運所有乘客。
直覺算法可能會想到做一個額外的陣列，同時遍歷所有給出的上下車陣列，在上車點到下車點間把乘客數加上去，最後檢查有沒有哪個里程點的時候乘客數量是超出車子的載客量。這樣的算法在遍歷每個上下車陣列的時候，都需要對做出的陣列做多個連續位置的加減，可以想見如果上下車典範圍拉遠、上下車陣列數量一多，會是十分費時的做法。
如昨天提到的，這邊我們利用差分陣列的思想，可以不必這樣每次頻繁加減整個區間。
1.建立差分陣列 diff，diff[i] 代表到達第 i 個點時人數的增減
2.遍歷上下車陣列，在 diff[上車] 的位置寫入上車的人數、在 diff[下車] 的位置減去下車的人數
3.遍歷 diff，累加所有 diff 元素，並逐個判斷累加過的總數是否大於載客量，如果大於載客量，表示該時間車上載不下所有需要上車的乘客，回傳失敗結果
4.遍歷完 diff，期間累加的總數沒有超過載客量，表示能夠順利載完客，回傳成功

public class Solution {
    public bool CarPooling(int[][] trips, int capacity) {
        var diff = new int[1001];//題目有註明里程最多到 1000，這邊定義一個 1001 的陣列方便操作
        for(var i = 0; i < trips.Length; i++){
            diff[trips[i][1]] += trips[i][0];
            diff[trips[i][2]] -= trips[i][0];
        }
        var sum = 0;
        for(var i = 0; i < diff.Length; i++){
            sum += diff[i];
            if(sum > capacity){
                return false;
            }
        }
        return true;
    }
}

差分陣列善於處理頻繁更新陣列中的區間的問題，透過維護差分陣列，我們能夠每次只更新差分陣列中變動區間左跟右的兩個位置的值，加上最後將主陣列(在上面的例子中剛好沒有主陣列，或是說主陣列是一個全零陣列)與差分陣列做比對，便能將所有應套用的數值變動反應到主陣列上。

二分搜尋

Binary Search
Leetcode 上就直接有一題是練習二分搜尋的，直接寫這題就可以了，二分搜尋的步驟如下：

找到當前陣列查找範圍的中間元素
比較目標元素與中間元素誰大
如果目標元素和中間元素一樣：找到答案、回傳索引
如果目標元素比中間元素小，把查找範圍變成開頭到中間元素前
如果目標元素比中間元素大，把查找範圍變成中間元素後到結尾
用新的查找範圍回到 1.，重複執行直到 2. 成功找到目標元素，或是當查找範圍為空，則脫出迴圈，並返回 -1(找不到目標元素)

public class Solution {
    public int Search(int[] nums, int target) {
        var left = 0;
        var right = nums.Length - 1;
        var mid = (left + right)/ 2;
        while(left <= right){
            mid = (left + right)/ 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
}

二分搜尋的細節在取區間的時候邊界的處理。
右邊邊界我這邊取的是 nums.Length - 1，也就是我是會包含右元素的判定，右邊元素也時實際元素，這裡影響了我的 While 的中止條件是 left <= right，也就是要 left > right 才終止(會有經過 left = right的這個時候，不遺漏右元素)，區間概念是左閉右閉，數學符號表示是 [ , ]。

另一種寫法是 right = nums.Length，While 的中止條件會改為 left < right，也就是不會走到 right 這元素(實際上在 right = nums.Length 的時候也就已經超出了陣列的索引)，區間概念是左閉右開，數學符號表示是 [ , )。同時如果用這種寫法的話，更新右邊邊界時不再是 right = mid - 1，而是 right = mid，因為實際上右邊界不會比較，是開的邊界。

至此前面 Day2 提到的陣列相關算法都結束了，明天我們會來聊一下陣列的變體，或是說多維應用 - 矩陣。